package nl.haemers.collections 
{
	import nl.haemers.collections.interfaces.IIterator;
	import nl.haemers.collections.interfaces.IListIterator;
	import nl.haemers.collections.interfaces.ICollection;
	import nl.haemers.collections.interfaces.IIterator;
	import nl.haemers.collections.interfaces.IList;
	import nl.haemers.collections.interfaces.IDeque;
	//import nl.haemers.collections.interfaces.ILinkedNode;
	import nl.haemers.collections.LinkedNode;
	
	import nl.haemers.collections.errors.NoSuchElementException;
	
	/**
	 * @author Jonathan Haemers
	 */
	public class LinkedList extends AbstractSequentialList implements IList, IDeque
	{
		//Because we can't create a Generic in AS3 we need a head for iteration as startpoint
		public var header				:LinkedNode;
		protected var _size				:int;
		
		public function LinkedList(collection:ICollection=null) 
		{
			if (collection)
			{
				addAll(collection);
			}
			else
			{
				//header = null; new LinkedNode(null, null, null);
				//header.next = header;
				//header.previous = header;
				//header.next = header.previous = header;
				_size = 0;
			}
		}
		
		/** Public methods **/
		override public function addAt(location:int, e:Object) : void 
		{
			if (location >= 0 && location <= _size) 
			{
				var link:LinkedNode = header;
				var i:int;
				//dividing numbers is slower then multiply
				if (location < (_size * .5)) 
				{
					for (i = location; i >= 0; i--) 
					{
						link = link.next;
					}
				} 
				else 
				{
					for (i = _size; i > location; i--) 
					{
						link = link.previous;
					}
				}
				
				var previous:LinkedNode = link.previous;
				var newLink:LinkedNode = new LinkedNode(e, previous, link);
				previous.next = newLink;
				link.previous = newLink;
				
				_size++;
				modCount++;
			} 
			else 
			{
				throw new RangeError();
			}
		}

		override public function add(e:Object) : Boolean
		{
			if (header)
			{
				//hmmm
				var oldLast:LinkedNode = (header.previous) ? header.previous : null;
				var newLink:LinkedNode = new LinkedNode(e, oldLast, header);
				header.previous = newLink;
				if (oldLast)
				{
					oldLast.next = newLink;
				}
				else
				{
					header.next = newLink;
				}
			}
			else
			{
				header = new LinkedNode(e);
				//header.previous = header;
				//header.next = header.previous = header;
			}
			_size++;
			modCount++;
			
			return true;
		}
		
		override public function addAll(collection:ICollection) : Boolean
		{
			var adding:int = collection.size;
			
			if (adding == 0) {
				return false;
			}
			
			var previous:LinkedNode = header.previous;
			var object:Object;
			var newLink:LinkedNode;
			
			for each (object in collection) 
			{
				newLink = new LinkedNode(object, previous, null);
				previous.next = newLink;
				previous = newLink;
			}
			
			previous.next = header;
			header.previous = previous;
			
			_size += adding;
			modCount++;
			
			return true;
		}
		
		override public function addAllAt(location:int, collection:ICollection):Boolean 
		{
			if (location < 0 || location > _size) 
			{
				throw new RangeError();
			}
			var adding:int = collection.size;
			if (adding == 0) 
			{
				return false;
			}
			
			var previous:LinkedNode = header;
			var i:int;
			//dividing numbers is slower then multiply
			if (location < (_size *.5)) 
			{
				//Backward looping is faster :)
				for (i = location; i >= 0; i--) 
				{
					previous = previous.next;
				}
			} 
			else 
			{
				for (i = _size; i >= location; i--) 
				{
					previous = previous.previous;
				}
			}
			
			var next:LinkedNode = previous.next;
			
			var object:Object;
			var newLink:LinkedNode;
			//TODO: possible it won't work cause of the Generics
			for each(object in collection) 
			{
				newLink = new LinkedNode(object, previous, null);
				previous.next = newLink;
				previous = newLink;
			}
			
			previous.next = next;
			next.previous = previous;
			
			_size += adding;
			modCount++;
			
			return true;
		}
		
		public function addFirst(e:Object) : void
		{
			var oldFirst:LinkedNode = header.next;
			var newLink:LinkedNode = new LinkedNode(e, header, oldFirst);
			header.next = newLink;
			oldFirst.previous = newLink;
			
			_size++;
			modCount++;
		}
		
		public function addLast(e:Object) : void
		{
			var oldLast:LinkedNode = header.previous;
			var newLink:LinkedNode = new LinkedNode(e, oldLast, header);
			
			header.previous = newLink;
			oldLast.next = newLink;
			
			_size++;
			modCount++;
		}
		
		override public function clear() : void
		{
			if (_size > 0)
			{
				header.next = header;
				header.previous = header;
				
				_size = 0;
				modCount++;
			}
		}
		//TODO: need to create a Cloneable Class before we override the function...
		//override public function clone() : Object
		public function clone() : LinkedList
		{
			/*
			try
			{
			*/
				var l:LinkedList = new LinkedList();//super.clone() as LinkedList;
				//l.size() = 0;
				l.header = new LinkedNode(null, null, null);
				l.header.previous = l.header;
				l.header.next = l.header;
				l.addAll(this);
				return l;
			// This won't happen because everything is cloneable
			/*
			}
			catch (e:CloneNotSupportedException)
			{
				return null;
			}
			*/
		}
		
		override public function contains(e:Object):Boolean 
		{
			var link:LinkedNode = header.next;
			if (e != null)
			{
				while (link != header)
				{
					if (e == link.element)
					{
						return true;
					}
					link = link.next;
				}
			}
			else
			{
				while (link != header)
				{
					if (link.element == null)
					{
						return true;
					}
				}
			}
			return false;
		}
		
		override public function get(location:int) : Object
		{
			if (location >= 0 && location < _size) 
			{
				var link:LinkedNode = header;
				var i:int;
				//split the list into 2 parts :)
				//dividing is slower then multiplieen
				if (location < (_size * .5))
				{
					//backwards looping is faster :)
					for (i = location; i >= 0; i--)
					{
						link = link.next;
					}
				}
				else
				{
					for (i = _size; i > location; i--)
					{
						link = link.previous;
					}
				}
				return link.element;
			}
			throw new RangeError();
		}
		
		public function getFirst() : Object
		{
			var first:LinkedNode = header.next;
			if (first != header)
			{
				return first.element;
			}
			throw new NoSuchElementException();
		}
		
		public function getLast() : Object
		{
			var last:LinkedNode = header.previous;
			if (last != header)
			{
				return last.element;
			}
			
			throw new NoSuchElementException();
		}
		
		override public function indexOf(e:Object) : int 
		{
			var location:int = 0;
			var link:LinkedNode = header.next;
			if (e != null)
			{
				while (link != header)
				{
					if (e == link.element)
					{
						return location;
					}
					link = link.next;
					location++;
				}
			}
			else
			{
				while (link != header)
				{
					if (link.element == null)
					{
						return location;
					}
					link = link.next;
					location++;
				}
			}
			return -1;
		}
		
		override public function lastIndexOf(e:Object) : int 
		{
			var location:int = _size;
			var link:LinkedNode = header.previous;
			if (e != null)
			{
				while (link != header)
				{
					location--;
					if (e == link.element)
					{
						return location;
					}
					link = link.previous;
				}
			}
			else
			{
				while (link != header)
				{
					location--;
					if (link.element == null)
					{
						return location;
					}
					link = link.previous;
				}
			}
			
			return -1;
		}
		//TODO: Implement ILinkIterator
		
		override public function listIteratorAt(location:int) : ListIterator 
		{
			return new ListIterator(0, this, location);
		}
		
		/*
			@Override
			public ListIterator<E> listIterator(int location) {
				return new LinkIterator<E>(this, location);
			}
		*/
		
		override public function removeAt(location:int) : Object 
		{
			if (location >= 0 && location < _size)
			{
				var link:LinkedNode = header;
				var i:int;
				//multiplieen is faster than dividing
				if (location < (_size * .5))
				{
					//backwards looping is faster
					for (i = location; i >= 0; i--)
					{
						link = link.next;
					}
				}
				else
				{
					for (i = _size; i > location; i--)
					{
						link = link.previous;
					}
				}
				var previous:LinkedNode = link.previous;
				var next:LinkedNode = link.next;
				previous.next = next;
				next.previous = previous;
				
				_size--;
				modCount++;
				
				return link.element;
			}				
			throw new RangeError();
		}
		
		override public function remove(e:Object=null) : Boolean 
		{
			if (e == null)
			{
				return removeFirst();
			}
			
			var link:LinkedNode = header.next;
			if (e != null)
			{
				while (link != header && e != link.element)
				{
					link = link.next;
				}
			}
			else
			{
				while (link != header && link.element != null)
				{
					link.next;
				}
			}
			if (link == header)
			{
				return false;
			}
			var next:LinkedNode = link.next;
			var previous:LinkedNode = link.previous;
			previous.next = next;
			next.previous = previous;
			
			_size--;
			modCount++;
			
			return true;
		}
		
		public function removeFirst() : Object
		{
			var first:LinkedNode = header.next;
			if (first != header)
			{
				var next:LinkedNode = first.next;
				header.next = next;
				next.previous = header;
				
				_size--;
				//modeCount++;
				
				return first.element;
			}
			throw new NoSuchElementException();
		}
		
		public function removeLast() : Object
		{
			var last:LinkedNode = header.previous;
			if (last != header)
			{
				var previous:LinkedNode = last.previous;
				header.previous = previous;
				previous.next = header;
				
				_size--;
				modCount++;
				
				return last.element;
			}
			throw new NoSuchElementException();
		}
		
		override public function set(location:int, e:Object):Object 
		{
			if (location >= 0 && location < _size)
			{
				var link:LinkedNode = header;
				var i:int;
				//multiplieen is faster then dividing
				if (location < (_size * .5))
				{
					//backwards looping is faster
					for (i = location; i >= 0; i--)
					{
						link = link.next;
					}
				}
				else
				{
					for (i = _size; i > location; i--)
					{
						link = link.previous;
					}
				}
				
				var result:Object = link.element;
				link.element = e;
				
				return result;
			}
			throw new RangeError();
		}
		//let's make it an getter instead of a method. 
		/**
		 * @see ICollection for detailed info
		 */
		override public function get size():int 
		{
			return _size;
		}
		
		public function offer(e:Object) : Boolean
		{
			add(e);
			return true;
		}
		
		public function offerFirst(e:Object) : Boolean
		{
			addFirst(e);
			return true;
		}
		
		public function offerLast(e:Object) : Boolean
		{
			addLast(e);
			return true;
		}
		
		public function poll() : Object
		{
			return _size > 0 ? removeFirst() : null;
		}
		
		public function pollFirst() : Object
		{
			return size > 0 ? removeFirst() : null;
		}
		
		public function pollLast() : Object
		{
			return size > 0 ? removeLast() : null;
		}
		
		public function peek() : Object
		{
			var first:LinkedNode = header.next;
			return first == header ?  null : first.element;
		}
		
		public function peekFirst() : Object
		{
			return size > 0 ? getFirst() : null;
		}
		
		public function peekLast() : Object
		{
			return size > 0 ? getLast() : null;
		}
		
		public function element() : Object
		{
			return getFirst();
		}
		
		override public function toArray() : Array 
		{
			var index:int = 0;
			var contents:Array = [];
			var link:LinkedNode = header.next;
			while (link != header)
			{
				contents[index++] = link.element;
				link = link.next;
			}
			return contents;
		}
		
		/** Typed arrays don't excist in AS3 maybe I could turn it into a vector?*/
		// TODO: Have a look at fake typed arrays.
		/*
		@Override
		@SuppressWarnings("unchecked")
		public <T> T[] toArray(T[] contents) {
			int index = 0;
			if (size > contents.length) {
				Class<?> ct = contents.getClass().getComponentType();
				contents = (T[]) Array.newInstance(ct, size);
			}
			Link<E> link = voidLink.next;
			while (link != voidLink) {
				contents[index++] = (T)link.data;
				link = link.next;
			}
			if (index < contents.length) {
				contents[index] = null;
			}
			return contents;
		}
		*/
	}
}